package classDesign;

import java.util.Scanner;


        /*
         * 递推方程：
         * dp[i][j] = min(max{dp[i][1]- dp[k][1],dp[k][j-1]})
         * */


public class test2 {
    public static int a[] = new int[100]; // 存放输入的n位整数
    public static int dp[][] = new int[1024][1024]; // dp中存放长度从1到n的所有划分结果的最大最小值，最后一个求得的dp[i][j]放置将i个数分成j段的最大最小值。。

    public static void main(String[] args) {
        int n, m, maxvalue = 0;
        Scanner input = new Scanner(System.in);
        n = input.nextInt();// 输入整数位数n
        m = input.nextInt();// 输入划分个数m

        for(int i = 1; i <= n; i++) {
            a[i] = input.nextInt();// 输入n位等待划分的正整数
        }
        for(int i = 1; i <= n; i++) {
            dp[i][1] = dp[i-1][1] + a[i];// dp[i][1]就是前i个数的和
        }

        for(int i = 1; i <= n; i++) {
            for(int j = 2; j <= m; j++){
                // 把i位整数划分成j段
                int minvalue = 99999; // 保存最小值用，要保存最小值就需要初始化成一个极大值
                for (int k = j - 1; k < i; k++) {
                    // K是划分位置，只用k划分成两段，因为划分得到的前半部分都是讨论过的。
                    int temp = Max(dp[i][1] - dp[k][1], dp[k][j-1]);
                    // 前j-1段的最大最小值为:dp[k][j-1];(前k个数划分成j-1段)
                    // 最后一段为：dp[i][1] - dp[k][1] ;(前i个数的和减去前K个数的和)
                    if(temp < minvalue) {
                        minvalue  = temp; // 保存最小值
                    }
                }
                dp[i][j] = minvalue; // 把所有k情况下的最小值赋值给dp[i][j]。
            }
        }
        System.out.println(dp[n][m]);
    }

    public static int Max(int a, int b) {
        if (a > b) {
            return a;
        }else {
            return b;
        }
    }
}

